#include <stdio.h>
//图的遍历之广度优先搜索 P196 P199
#define MAXSIZE 100
typedef char ElemType;
//图的声明
typedef struct 
{
    ElemType vertex[MAXSIZE];
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
//图的创建
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=15;
    //顶点：按照深度优先遍历的顺序
    g->vertex[0]='A';
    g->vertex[1]='B';
    g->vertex[2]='C';
    g->vertex[3]='D';
    g->vertex[4]='E';
    g->vertex[5]='F';
    g->vertex[6]='G';
    g->vertex[7]='H';
    g->vertex[8]='I';
    //边：
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            g->edge[i][j]=0;
        }
    }
    //A-B A-F
    g->edge[0][1]=1;
    g->edge[0][5]=1;
    //B-C B-G B-I
    g->edge[1][2]=1;
    g->edge[1][6]=1;
    g->edge[1][8]=1;
    //C-D C-I
    g->edge[2][3]=1;
    g->edge[2][8]=1;
    //D-E D-G D-H D-I
    g->edge[3][4]=1;
    g->edge[3][6]=1;
    g->edge[3][7]=1;
    g->edge[3][8]=1;
    //E-F E-H
    g->edge[4][5]=1;
    g->edge[4][7]=1;
    //F-G
    g->edge[5][6]=1;
    //G-H
    g->edge[6][7]=1;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
//图的广度遍历
int visited[MAXSIZE]={0};
/*
void bfs(mat_graph g)
{
    //用数组模拟队列：数组中存储顶点数组下标，也是边数组的行数
    int queue[MAXSIZE]={0};
    int front=0;
    int rear=0;
    int i=0;//代表顶点数组下标，也是边数组的行数
    queue[front]=i;
    rear++;
    visited[i]=1;
    int j; //代表边数组的列数
    while(rear!=front)
    {
        int num=rear-front;
        while(num>0)
        {
            i=queue[front]; //相当于保留出队元素
            printf("%c",g.vertex[i]);
            for(j=0;j<g.vertex_num;j++)
            {
                if(g.edge[i][j]==1&&visited[j]==0)
                {
                    queue[rear]=j;
                    rear++;
                    visited[j]=1;
                }
            }
            front++;
            num--;
        }
    }
}
*/
//简化：先打印再入队
void bfs(mat_graph g)
{
    //用数组模拟队列：数组中存储顶点数组下标，也是边数组的行数
    int queue[MAXSIZE]={0};
    int front=0;
    int rear=0;
    int i=0;//代表顶点数组下标，也是边数组的行数
    printf("%c",g.vertex[i]);
    queue[rear]=i;
    rear++;
    visited[i]=1;
    int j; //代表边数组的列数
    while(rear!=front)
    {
        i=queue[front];//相当于保留出队元素
        for(j=0;j<g.vertex_num;j++)
        {
            if(g.edge[i][j]==1&&visited[j]==0)
            {
                printf("%c",g.vertex[j]);
                visited[j]=1;
                queue[rear]=j;
                rear++;
            }
        }
        front++;
    }  
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    bfs(g);
    return 0;
}
//输出：ABFCGIEDH
//因为类似于二叉树的层次遍历，所以采用队列，但因为创建一个队列太复杂麻烦了，我们就用数组模拟队列
//又因为在找顶点与顶点的边关系时，要用行数和列数，而行数和列数正是顶点数组下标
//所以我们把顶点下标（行数）入队，这样我们就可以根据出队数据找到那个顶点边数组的那一行
//同时，可能有一个疑问？P196中广度顺序是：ABFCIGEDH，那为什么我们输出时CIG顺序变了？
//在同一层中无需考虑顶点顺序，我们只要保证上一层顶点整体先于下一层顶点即可。
